/* 
 * File:   auxiliaire.c
 * Author: FENG Xu <fengxu1989@gmail.com>
 *
 * Created on May 29, 2012, 5:48 PM
 */
#include <stdio.h>
#include <stdlib.h>
#include "../h/auxiliaires.h"

/*
 * creer un nouvel element de listeSP.
 */
listeSP newLSP(unsigned char symbole, int poids, listeSP suivant){
	listeSP lsp=(listeSP)malloc(sizeof(struct _listeSP));
	lsp->symbole=symbole;
	lsp->poids=poids;
	lsp->suivant=suivant;
	return lsp;
}

/*
 * cloner une listeSP.
 */
listeSP clonerLSP(listeSP lsp){
	listeSP nouv=NULL;
    listeSP prec,courant= NULL;
	listeSP courantLSP=lsp;

    if (courantLSP!=NULL){
        nouv = newLSP(courantLSP->symbole,courantLSP->poids,NULL);
        prec=nouv;
        courantLSP=courantLSP->suivant;
    }

    while (courantLSP!=NULL){
						printf("ICI1 %p\n",courantLSP);
						
        courant=newLSP(courantLSP->symbole,courantLSP->poids,NULL);
						printf("ICI2\n");

		prec->suivant= courant;
		prec=courant;
        courantLSP=courantLSP->suivant;
		
    }

	return nouv;
}

/*
 * creer un nouvel ajout.
 */
ajout newAjout(int poidsSomme, int nbSymboles, listeSP tete){
	ajout a=(ajout)malloc(sizeof(struct _ajout));
	a->poidsSomme=poidsSomme;
	a->nbSymboles=nbSymboles;
	a->tete=tete;
	return a;
}

/*
 * cloner un ajout.
 */
ajout clonerAjout(ajout a){
	return newAjout(a->poidsSomme, a->nbSymboles, clonerLSP(a->tete));
}

/*
 * trier un tableau d'ajouts en fonction du poidsSomme de chaque ajout et du nombre de symboles des ajouts.
 * tri par insertion. 
 */
void trierTabAjouts(ajout* tab){
	int i, j;
	ajout x=NULL;
	if(tab[0]!=NULL && tab[1]!=NULL){
		i=0;
		while(i<LMAX && tab[i]!=NULL){
			x=tab[i];
			j=i;
			while(j>0 && ((tab[j-1]->poidsSomme)>(x->poidsSomme)
							||((tab[j-1]->poidsSomme)==(x->poidsSomme) 
								&& (tab[j-1]->nbSymboles)>(x->nbSymboles)))){
				tab[j]=tab[j-1];
				j--;
			}
			tab[j]=x;
			i++;
		}
	}
}

/*
 * inserer un ajout dans le tableau d'ajouts et trier le tableau.
 */
void insererEnTriant(ajout* tab, ajout a){
	if(a!=NULL){
		int i=0;
		while(i<LMAX && tab[i]!=NULL){
			i++;
		}
		if(tab[i]==NULL) tab[i]=clonerAjout(a);
		trierTabAjouts(tab);
	}
}

/*
 * concatener deux listeSP
 */
listeSP concatener(listeSP l1, listeSP l2){
	listeSP concat=NULL;
	listeSP courant=NULL;
	if(l1!=NULL){
		concat=l1;
		courant=l1;
		while(courant->suivant!=NULL){
			courant=courant->suivant;
		}
		courant->suivant=l2;
		free(l2);
	}
	else{
		concat=l2;
	}
	return concat;
}

/*
 * creer un ajout qui appaire le 2i-ieme element et 2i+1-ieme element d'un tabAjouts, et renvoie l'ajout.
 */
ajout appairer(ajout* tab, int i){
	return newAjout(tab[i*2]->poidsSomme+tab[i*2+1]->poidsSomme, tab[i*2]->nbSymboles+tab[i*2+1]->nbSymboles, concatener(clonerLSP(tab[i*2]->tete), clonerLSP(tab[i*2+1]->tete)));
}

/*
 * Fonction trierLSL (tri par selection du minimum) : cette fonction trie la liste symbole /longueur par ordre croissant de longueur 
 */
void trierLSL(listeSL list){
   listeSL i,j,min; /* On declare 3 pointeurs */
   int tmpL;
   unsigned char tmpS;
   
   for (i=list; i != NULL; i=i->suivant){ /*On fait un parcours de liste symbole/longueur en partant de la tete */
       min=i; /* La minimum pointe vers le premier element de la liste */ 
       for (j=i->suivant; j != NULL; j=j->suivant){ /* On fait un parcours en partant de l'element suivant la tete */
           if (j->longueur < min->longueur) min=j;    
           if (min != i){ 
			   tmpL=i->longueur;
			   i->longueur=min->longueur;
			   min->longueur=tmpL;
			   
			   tmpS=i->symbole;
			   i->symbole=min->symbole;
			   min->symbole=tmpS;
           }
       }
   }  
}

/*
 * creer un nouvel element de listeSC
 */
listeSC newLSC(unsigned char symbole, unsigned char code, int longueur, listeSC suivant){
	listeSC lsc=(listeSC)malloc(sizeof(struct _listeSC));
	lsc->symbole=symbole;
	lsc->code=code;
	lsc->longueur=longueur;
	lsc->suivant=suivant;
	return lsc;
}

/*
 * creer un nouvel element de listeSL 
 */
listeSL newLSL(unsigned char symbole, int longueur, listeSL suivant){
    listeSL sl=(listeSL)malloc(sizeof(struct _listeSL));
    sl->symbole=symbole;
    sl->longueur=longueur;
    sl->suivant=suivant;
    return sl;
}
